package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * 1922. 统计好数字的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/15 12:49
 */
public class CountGoodNumbers {

    public static void main(String[] args) {
        CountGoodNumbers test = new CountGoodNumbers();

        // 400
//        long n = 4;

        // 564908303
        long n = 50;

        int i = test.countGoodNumbers(n);
        System.out.println(i);
    }

    public int countGoodNumbers(long n) {
        if (n == 1) {
            return 5;
        }
        if (n == 2) {
            return 20;
        }
        long sum = 1;
        if ((n & 1) == 1) {
            sum = 5;
        }
        n >>= 1;
        if ((n & 1) == 1) {
            sum = sum * 20;
        }
        n >>= 1;
        long item = 20;
        while (n != 0) {
            item = (item * item) % 1000000007;
            if ((n & 1) == 1) {
                sum = (item * sum ) % 1000000007;
            }
            n >>= 1;
        }
        return (int) sum;
    }

}
